package org.ymx.myMap;

import java.util.Scanner;

public class HashTableDemo {

    public static void main(String[] args) {
        HashTab hashtab = new HashTab(7);
        String key = "";
        Scanner sr = new Scanner(System.in);
        while (true) {
            System.out.println("add:增加雇员，list：显示雇员，find:查找雇员，exit：退出");
            key = sr.next();
            switch (key) {
                case "add":
                    System.out.println("请输入雇员id：");
                    int id = sr.nextInt();
                    System.out.println("请输入雇员name：");
                    String name = sr.next();
                    Emp emp = new Emp(id, name);
                    hashtab.add(emp);
                    break;
                case "list":
                    hashtab.list();
                    break;
                case "find":
                    System.out.println("请输入要查找雇员的id：");
                    int findId = sr.nextInt();
                    hashtab.findEmpById(findId);
                    break;
                case "exit":
                    sr.close();
                    System.exit(0);
                    break;
                default:
                    break;
            }
        }
    }

}

//创建一个哈希表
class HashTab {
    private EmpLinkedList[] empLinkedList;
    private int size;

    public HashTab(int size) {
        this.size = size;
        empLinkedList = new EmpLinkedList[size];
        for (int i = 0; i < size; i++) {
            empLinkedList[i] = new EmpLinkedList();
        }
    }

    // 根据员工的id得到应该添加到哪条链表
    public void add(Emp emp) {
        // 得到emp对应的链表
        int EmpLinkedListNum = hashFun(emp.id);
        empLinkedList[EmpLinkedListNum].add(emp);
    }

    // 编写散列函数
    public int hashFun(int id) {
        return id % size;
    }

    // 遍历hashTab
    public void list() {
        for (int i = 0; i < size; i++) {
            empLinkedList[i].list(i);
        }
    }

    // 根据id查找在哈希表中对应的链表
    public void findEmpById(int id) {
        int EmpLinkedListNum = hashFun(id);
        Emp emp = empLinkedList[EmpLinkedListNum].findEmpById(id);
        if (emp == null) {
            System.out.println("在链表中为找到该节点\n");
        } else {
            System.out.printf("id为%d的员工在第%d条链表中\n", id, EmpLinkedListNum + 1);
        }
    }
}

//创建雇员信息
class Emp {
    public int id;
    public String name;
    public Emp next = null;

    public Emp(int id, String name) {
        super();
        this.id = id;
        this.name = name;
    }
}

class EmpLinkedList {
    private Emp head;// 定义一个头指针指向链表的第一个元素
    // 创建一个方法将emp加入到链表中

    public void add(Emp emp) {
        if (head == null) {// 链表中第一个节点为空
            head = emp;
            return;
        }
        Emp curEmp = head;// 创建一个辅助节点，因为head不能变化
        while (true) {
            if (curEmp.next == null) {// 找到链表的最后
                break;
            }
            curEmp = curEmp.next;// 将指针curEmp后移
        }
        curEmp.next = emp;// 将emp加入链表

    }

    // 遍历链表
    public void list(int no) {
        if (head == null) {
            System.out.printf("链表%d为空\n", no + 1);
            return;
        }
        System.out.printf("第%d条链表信息为：", no + 1);
        Emp curEmp = head;// 辅助指针
        while (true) {
            System.out.printf("==>id=%d name = %s\t", curEmp.id, curEmp.name);
            if (curEmp.next == null) {// 到链表最后
                break;
            }
            curEmp = curEmp.next;// 后移
        }
        System.out.println();
    }

    public Emp findEmpById(int id) {
        if (head == null) {
            System.out.println("链表为空");
            return null;
        }
        Emp curEmp = head;
        while (true) {
            if (curEmp.id == id) {// 找到要查找的节点
                break;
            }
            if (curEmp.next == null) {
                curEmp = null;
                break;
            }
            curEmp = curEmp.next;
        }
        return curEmp;
    }
}

